package 树;

/**
 * https://leetcode-cn.com/problems/maximum-binary-tree/
 */
public class _654_最大二叉树 {
    public class TreeNode {
       int val;
       TreeNode left;
       TreeNode right;
       TreeNode() {}
       TreeNode(int val) { this.val = val; }
       TreeNode(int val, TreeNode left, TreeNode right) {
           this.val = val;
           this.left = left;
           this.right = right;
       }
    }

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        if(nums == null || nums.length == 0) return null;

        return build(nums,0,nums.length-1);
    }


    //函数定义：输入一个数组，索引[begin,end],构造以root为根节点的二叉树并返回根节点
    private TreeNode build(int[] nums,int begin,int end){
        if(begin > end) return null; //base case

        int index = -1; //最大值所在的索引
        int maxVal = Integer.MIN_VALUE;
        //迭代数组找到当前数组最大值和它所在的索引
        for(int i=begin;i<=end;++i){
            if(maxVal < nums[i]){
                index = i;
                maxVal = nums[i];
            }
        }
        //构造根节点
        TreeNode root = new TreeNode(maxVal);
        //分解问题：递归的去构造左子树的根节点和右子树的根节点
        root.left = build(nums,begin,index-1);
        root.right = build(nums,index+1,end);

        return root;
    }
}
